I. Field of the Invention
The present invention relates to image data compression and more particularly to reducing distortion in images which are data compressed and reconstructed using predictive coding methods.
II. Description of the Problem
Typically an image is represented as rows of picture elements referred to as "pixels" or "pels". To characterize the image as digital data, a feature (e.g., luminance, red intensity, blue intensity, or the like) of each pixel is normally represented by a value referred to as a "graylevel" value. For luminance, the graylevel value ranges from white to black over a plurality of steps. For example, in an eight bit representation, each pixel may be represented by a graylevel value from between 0 and 255 (2.sup.8 -1). For an image having 512 pixels per row and 480 rows, a total of 512.times.480.times.8=1966080 bits would be required to represent all of the pixels in an image. This is a form of pulse code modulation (PCM).
In applications in which image data is to be transferred quickly and/or is to be contained in limited storage, it is often required to represent the graylevel information for the pixels in an image by less than the nearly two million bits indicated above. The process of reducing the required number of bits is referred to as image data compression. Associated with data compression is a complementary process (i.e., decompression) by which the original pixel values can be approximated from the compressed data.
One prior art method of compressing image data involves predictive coding. According to the basic teachings of predictive coding, a predicted value--based on one or more neighboring pixel values--is determined for a "current" pixel (i.e., a pixel which is currently being processed). The difference D between the original graylevel value for the current pixel and the predicted value therefor is mapped to a corresponding quantization level of a previously defined quantization table. In the quantization table, each of various ranges of difference values is designated by a corresponding QN level (where N is the level). For example, QN=Q0 corresponds to difference values that extend over a first range; QN=Q1 corresponds to difference values extending over a second range; and so on. Typically, the QN levels in the quantizer table are symmetrical about the QO level. For simplicity, reference is made to only the "positive" portion of the quantizer table in which N.gtoreq.0 (e.g. Q0, Q1, Q2, and so on). Each level has a predefined value associated therewith; for example, Q0 may be designated as 0; Q1 may be designated as 4; Q2 may be designated as 12; and so on. (Due to the aforementioned symmetry, the first quantizer level below Q0 has a value of -Q1 VALUE, or -4; the second quantizer level below Q0 has a value of -12; and so on). Accordingly, if the magnitude of the difference value for a given pixel is in the first range, the predictive coder selects QN=Q0 and the value designated therefor (namely 0) is provided. Similarly, if the difference value for a given pixel is in the second (positive) range, QN=Q1 and the designated value therefore (namely 4) is provided. Rather than an 8-bit PCM representation, predictive coding provides that the designated value for the QN level serve to represent the graylevel of a pixel. A specific known type of predictive coding is differential pulse code modulation (DPCM).
In accordance with predictive coding, by looking at the value for QN rather than the original (8-bit) graylevel value, the pixel data is greatly compressible.
Another prior art data compression technique, which is often used in combination with predictive coding, is referred to as "entropy coding" or "variable-length coding". In entropy coding, the number of bits used in representing events is intended to be inversely related to event probability. In a predictive coding context, entropy coding is applied to the quantization levels (or designated values therefor). That is, the more probable quantization levels are represented by code-words characterized by relatively short lengths (of bits), whereas less probable quantization levels are represented by relatively longer lengths. The correct assignment of code-word lengths is dictated by information theory concepts; however, it should be intuitively clear that the more often the short code-words get used, the better the compression. In this regard, in images where areas of uniform graylevel are common, the most probable quantization level will be QN=Q0 (where Q0=0) and the shortest codeword is assigned to that event.
One further aspect of predictive coding is reconstructing graylevel values for pixels after the original values therefor have been predictively coded. In generating a reconstructed value for a "current" pixel, the predicted value thereof P and the value designated for the quantization level (e.g., Q1=4) are summed. The reconstructed value X' should be close to the original input value X but may differ. Because D and its assigned QN VALUE may differ, the original value X=(D+P) and the reconstructed value X'=(P+QN VALUE) may differ. The largest difference depends on the range of D values being quantized to a given QN VALUE.
Significantly, different pixels having an original graylevel value of X may have differing respective reconstructed values X'. Moreover, in predictive coding, successive pixels in a row located in an area of uniform original graylevel will tend to have the same X' value; the reconstructed value X' propagating along the row. If a first row propagates a reconstructed value X'.sub.1, a second row propagates another reconstructed value X'.sub.2, and a third row propagates its own respective reconstructed value X'.sub.3, the pixels in each row will display graylevels of slightly different magnitudes. If the magnitudes are sufficiently different to be perceptible, the variations will be seen as distortion, or streaking, in an image formed from reconstructed pixel values.
Viewed in another way, if the range of difference values corresponding to the Q0 level is wide, possible variation between respective reconstructed values X' of rows in an area of originally uniform graylevel is correspondingly great. In such event, streaking becomes a problem.
Reducing the range of difference values assigned to the Q0 level would appear, at first blush, to be a solution to the streaking problem. If the Q0 level range of difference values is sufficiently small, any variation in reconstructed pixel value from one line to another would not be perceived.
However, by shrinking the range of the Q0 level, there is a great loss in data compression.
This leads to a dilemma: to achieve more data compression, the range of difference values assigned to the Q0 level should be broad; however, a broad range of difference values for Q0 can result in streaking. In areas of low image activity (that is, areas where pixels have substantially uniform original graylevel values), achieving data compression without perceptible streaking has been a significant problem.
A further problem relating to distortion in the form of streaking involves a phenomenon referred to as "Mach-banding". In particular, graylevel "step" transitions in an image are typically exaggerated when viewed by a human. The difference between two graylevels--at a step transition--thus appears greater than the actual difference therebetween and provides undesired distortion.
A three-pass postprocessor filter has been suggested by the prior technology to address the problem of the exaggerated perception of streaks. However, the three-pass technique requires lengthy execution time. The first pass is a nearest neighbor filter, the second pass is a two nearest neighbor filter, and the third pass is a four nearest neighbor filter. Even without employing the third pass, the second pass two nearest neighbor filter requires 17 seconds on an IBM PC-AT, using a highly optimized register intensive assembly language implementation. A full software implementation of the original post-processing filter is thus impractical.